package Algorithm.SingleStack;

import java.util.ArrayDeque;
import java.util.Deque;

//84. 柱状图中最大的矩形
//https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
public class Leetcode84_notice_largest_rectangle_in_histogram {
    //单调栈两次遍历
    class Solution {
        public int largestRectangleArea(int[] heights) {
            int n = heights.length;
            int[] left = new int[heights.length];
            int[] right = new int[heights.length];

            Deque<Integer> stack = new ArrayDeque<Integer>();
            for(int i = 0; i < n; i++){
                while(!stack.isEmpty() && heights[stack.peek()] >= heights[i]){
                    stack.pop();
                }
                left[i] = (stack.isEmpty() ? -1 : stack.peek());
                stack.push(i);
            }

            stack.clear();

            for(int i = n - 1; i >= 0; i--){
                while(!stack.isEmpty() && heights[stack.peek()] >= heights[i]){
                    stack.pop();
                }
                right[i]  = (stack.isEmpty() ? n : stack.peek());
                stack.push(i);
            }

            int ans = 0;
            for(int i = 0; i < n; i++){
                ans = Math.max(ans, (right[i] - left[i] -1) * heights[i]);
            }

            return ans;
        }
    }

    //单调栈一次遍历
    class Solution2 {
        public int largestRectangleArea(int[] heights) {
            int n = heights.length;
            int[] left = new int[heights.length];
            int[] right = new int[heights.length];

            Deque<Integer> stack = new ArrayDeque<Integer>();

            for(int i=0;i<heights.length;i++){
                right[i] = heights.length;
                while(!stack.isEmpty() && heights[stack.peek()]>=heights[i]){
                    int index = stack.pop();
                    right[index] = i;
                }

                left[i] = stack.isEmpty()?-1:stack.peek();
                stack.push(i);

            }

            int ans = 0;

            for(int i=0;i<heights.length;i++){
                ans = Math.max(ans,(right[i]-left[i]-1)*heights[i]);
            }

            return ans;
        }
    }
}
